package com.lzq.leetcode.lanqiao;

import java.util.Arrays;
import java.util.Scanner;

public class s1024 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        String input = scan.nextLine();

        String[] names = input.split("(?=[A-Z])");

        int len = names.length;

        String[] dp = new String[len];
        int[] path = new int[len];
        // 遍历获取最长的公共字串
        dp[0] = names[0];
        path[0] = 0;
        int max = 0;

        for (int i=1; i<len; i++) {
            if (names[i].compareTo(dp[max]) > 0) {
                // 直接添加到后面
                dp[++max] = names[i];
                path[i] = max;
            } else {

                // 二分查找
                int l = 0;
                int r = max;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (dp[mid].compareTo(names[i]) >= 0) {
                        r = mid - 1;
                    } else {
                        l = mid + 1;
                    }
                }
                dp[l] = names[i];
                path[i] = l;
            }
        }

        Arrays.stream(dp).forEach(System.out::println);

        int[] ans = new int[max+1];
        int k = 0;
        // 一定要从后往前遍历，因为最长字符串长度的第k - 1个位置的字符串，或许有多个答案，但为了字典序列最小，正确的答案肯定排在最后面的，准确来说应该是在 靠近 最靠后的第k个位置 的 第k-1个位置，这话有些绕口
        // 因为只有字典序列越小，才会替换掉前面的字符串，形成新的位置排在后面
        for (int i = len - 1; i >= 0; i--) {
            if (max < 0)
                break;
            if (max == path[i]) { // index长度就对应位置
                ans[k] = i;
                k++;
                max--;
            }
        }
        for (int i = k - 1; i >= 0; i--) {
            System.out.print(names[ans[i]]);
        }

    }
}
